package DynamicProgramming;

import java.util.HashMap;
import java.util.Map;

public class _494_TargetSum {
    // depth first method:over time limited, using map
    /**

    Map<Integer, Integer> maps;
    int len;
    int[] nums;

    public int findTargetSumWays_o1(int[] nums, int S) {
        this.maps = new HashMap<>();
        this.len = nums.length;
        this.nums = nums;
        dfs_o1(0, 0);
        return maps.getOrDefault(S, 0);
    }

    public void dfs_o1(int pos, int sum) {
        if (pos == len) {
            maps.put(sum, maps.getOrDefault(sum, 0) + 1);
        } else {
            dfs_o1(pos + 1, sum + nums[pos]);
            dfs_o1(pos + 1, sum - nums[pos]);
        }
    }
    **/
    int[] counts;
    int len;
    int[] nums;
    public int findTargetSumWays_1(int[] nums, int S) {
        this.counts = new int[2000];
        this.len = nums.length;
        this.nums = nums;
        dfs(0, 0);
        return S>1000?0:counts[S + 1000];
    }

    public void dfs(int pos, int sum) {
        if (pos == len) {
            counts[sum + 1000]++;
        } else {
            dfs(pos + 1, sum + nums[pos]);
            dfs(pos + 1, sum - nums[pos]);
        }
    }

    //method 2:dynamic programming
    public int findTargetSumWays(int[] nums, int S) {
        int[][] dp = new int[nums.length][2001];
        dp[0][nums[0] + 1000] = 1;
        dp[0][-nums[0] + 1000] += 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = -1000; j <= 1000; j++) {
                if (dp[i - 1][j + 1000] > 0) {
                    dp[i][j + nums[i] + 1000] += dp[i - 1][j + 1000];
                    dp[i][j - nums[i] + 1000] += dp[i - 1][j + 1000];
                }
            }
        }
        return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
    }

}
